﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Galoap
{
    /// <summary>
    /// A  class to model the Tree
    /// </summary>
    public class Tree
    {
        /// <summary>
        /// The ontology
        /// </summary>
        public Ontology Ontology { get; set; } 

        /// <summary>
        /// the index
        /// </summary>
        public int Index { get; set; }  

        /// <summary>
        /// The list of childs
        /// </summary>
        public Tree[] Child { get; set; } 

        /// <summary>
        /// for each child his phrases mix with the index of this sorted
        /// </summary>
        public int[][] SubPhrases { get; set; } 

        /// <summary>
        /// his index mix with the phrases of all child sorted
        /// </summary>
        public int[] Phrases { get; set; }

        /// <summary>
        /// the parent
        /// </summary>
        public Tree Parent { get; set; } 

        /// <summary>
        /// the level
        /// </summary>
        public int Level { get; set; }

        /// <summary>
        /// the index in the list of the parent
        /// </summary>
        public int Child_index { get; set; }

        /// <summary>
        /// flag true if the node is visited
        /// </summary>
        public bool Visited { get; set; }

        /// <summary>
        /// The constructor
        /// </summary>
        /// <param name="o">the ontology</param>
        /// <param name="i">the index in the phrase</param>
        /// <param name="parent">the parent</param>
        /// <param name="level">the level of deepness</param>
        /// <param name="child_index">the index in the list of the parent</param>
        public Tree(Ontology o, int i, Tree parent, int level, int child_index)
        {
            this.Ontology = o;
            this.Index = i;
            this.Parent = parent;
            this.Level = level;
            this.Visited = false;
            this.Child = null;
            this.Child_index = child_index;
        }

        /// <returns>true if has child to visit</returns>
        public bool HasChildToVisit()
        {
            foreach (Tree t in Child)
            {
                if (!t.Visited)
                    return true;
            }
            return false;
        }

        /// <returns>true if has parent</returns>
        public bool HasParent()
        {
            return Parent != null;
        }

        /// <summary>
        /// Get the deepest child
        /// <returns>the deepest child, null if the childs are visited, this if the node has no child</returns>
        public Tree GetDeepestChild()
        {
            if (this.Child.Length == 0) // a leaf
            {
                return this;
            }
            else
            {
                Tree max = null;
                Tree temp = null;
                foreach (Tree t in Child)
                {
                    if (!t.Visited)
                    {
                        temp = t.GetDeepestChild();
                        if ((max == null) || (temp.Level > max.Level))
                            max = temp;
                    }
                }
                return max;

            }
        }

        /// <summary>
        /// Create the SubPhrases and Phrases of the tree
        /// </summary>
        /// <returns>An array of index representing the phrases</returns>
        public int[] SetSubPhrases()
        {
            if (this.Child.Length == 0) // a leaf
            {
                this.SubPhrases = null;
                this.Phrases = new int[1] { this.Index };
            }
            else
            {
                int length = 0;
                int[] temp;
                SubPhrases = new int[Child.Length][];
                int j = 0;
                foreach (Tree t in Child)
                {
                    temp = Tree.AddSort(this.Index, t.SetSubPhrases());
                    SubPhrases[j]=temp;
                    length += temp.Length;
                    j++;

                }
                int[] r = new int[length - SubPhrases.Length + 1];

                int start = 0;
                foreach (int[] sub in SubPhrases)
                {
                    r = CopyExcept(this.Index, sub, r, start);
                    start += sub.Length - 1;
                }
                r[r.Length - 1] = this.Index;

                Array.Sort(r);
                this.Phrases = r;
            }
            return this.Phrases;
        }

        /// <summary>
        /// copy a into b starting from start except of n
        /// </summary>
        /// <param name="n">number to avoid</param>
        /// <param name="a">array in input</param>
        /// <param name="b">output array</param>
        /// <param name="start">position from where start to copy in b</param>
        /// <returns>an array not sorted</returns>
        private static int[] CopyExcept(int n, int[] a, int[] b, int start)
        {
            int j = start;
            for (int i = 0; i < a.Length; i++)
            {
                if (a[i] != n)
                {
                    b[j] = a[i];
                    j++;
                }
            }
            return b;
        }

        /// <summary>
        /// insert n into a and sort, a is already sorted
        /// </summary>
        /// <param name="n">number to insert</param>
        /// <param name="a">array, must be sorted!</param>
        /// <returns>an array b sorted</returns>
        private static int[] AddSort(int n, int[] a)
        {
            bool found = false;
            int[] b = new int[a.Length + 1];
            for (int i = 0; i < b.Length; i++)
            {
                if ((i == b.Length - 1) && (!found))
                {
                    b[b.Length - 1] = n;
                }
                else
                {
                    if ((!found) && (i < a.Length) && (a[i] >= n))
                    {
                        b[i] = n; b[i + 1] = a[i]; i++; found = true;
                    }
                    else
                    {
                        if (found)
                            b[i] = a[i - 1];
                        else
                            b[i] = a[i];
                    }
                }
            }
            return b;
        }


        /// <summary>
        /// override to string
        /// </summary>
        /// <returns>string</returns>
        public override string ToString()
        {
            return Ontology.ToString();
        }
    }
}